//除自身以外数组的乘积
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) 
    {
        //f[i]表示 [0,i-1]内所有元素的积
        //g[i]表示 [i+1,n-1]内所有元素的积
        int n=nums.size();
        vector<int>res(n);
        vector<int>f(n,1);
        vector<int>g(n,1);
        for(int i=1;i<n;i++)
        {
            f[i]=f[i-1]*nums[i-1];
        }
        for(int j=n-2;j>=0;j--)
        {
            g[j]=g[j+1]*nums[j+1];
        }
        for(int i=0;i<n;i++)
        {
            res[i]=f[i]*g[i];
        }
        return res;
    }
};
//和为k的子数组
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        //dp[i]以 nums的前i个数的总和
        //  超时了
        // vector<int>dp(nums.size()+1,0);
        // for(int i=1;i<=nums.size();i++) dp[i]=dp[i-1]+nums[i-1];
        // int res=0;
        // for(int i=1;i<=nums.size();i++)
        // {
        //     for(int j=0;j<=i-1;j++)
        //     {
        //         if(dp[i]-dp[j]==k) res++;
        //     }
        // }
        // return res;
        unordered_map<int,int>hash;
        hash[0]=1;
        int sum=0;
        int res=0;
        for(int i=0;i<nums.size();i++)
        {
            sum+=nums[i];
            if(hash.find(sum-k)!=hash.end())
            {
                res+=hash[sum-k];
                hash[sum]++;
            }
            else
            {
                hash[sum]++;
            }
        }
        return res;
    }
};
